{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Complete Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countCompleteSubstrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计完全子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>word</code>&nbsp;和一个整数 <code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果&nbsp;<code>word</code>&nbsp;的一个子字符串 <code>s</code>&nbsp;满足以下条件，我们称它是 <strong>完全字符串：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s</code>&nbsp;中每个字符 <strong>恰好</strong>&nbsp;出现 <code>k</code>&nbsp;次。</li>\n",
    "\t<li>相邻字符在字母表中的顺序 <strong>至多</strong>&nbsp;相差&nbsp;<code>2</code>&nbsp;。也就是说，<code>s</code>&nbsp;中两个相邻字符&nbsp;<code>c1</code> 和&nbsp;<code>c2</code>&nbsp;，它们在字母表中的位置相差<strong>&nbsp;至多</strong>&nbsp;为 <code>2</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <code>word</code>&nbsp;中 <strong>完全</strong>&nbsp;子字符串的数目。</p>\n",
    "\n",
    "<p><strong>子字符串</strong>&nbsp;指的是一个字符串中一段连续 <strong>非空</strong>&nbsp;的字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>word = \"igigee\", k = 2\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>完全子字符串需要满足每个字符恰好出现 2 次，且相邻字符相差至多为 2 ：<em><strong>igig</strong></em>ee, igig<strong style=\"font-style: italic;\">ee</strong>, <em><strong>igigee</strong>&nbsp;。</em>\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>word = \"aaabbbccc\", k = 3\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>完全子字符串需要满足每个字符恰好出现 3 次，且相邻字符相差至多为 2 ：<em><strong>aaa</strong></em>bbbccc, aaa<em><strong>bbb</strong></em>ccc, aaabbb<em><strong>ccc</strong></em>, <em><strong>aaabbb</strong></em>ccc, aaa<em><strong>bbbccc</strong></em>, <em><strong>aaabbbccc </strong></em>。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= word.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>word</code>&nbsp;只包含小写英文字母。</li>\n",
    "\t<li><code>1 &lt;= k &lt;= word.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-complete-substrings](https://leetcode.cn/problems/count-complete-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-complete-substrings](https://leetcode.cn/problems/count-complete-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"igigee\"\\n2', '\"aaabbbccc\"\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteSubstrings(self, word: str, k: int) -> int:\n",
    "        n = len(word)\n",
    "        a = [ord(c) - ord('a') for c in word]\n",
    "    \n",
    "        ans = 0\n",
    "        start = 0  # 当前连续段的开头(相邻差<=2)\n",
    "        a.append(100)\n",
    "        def f(start,end):\n",
    "            ans = 0\n",
    "            for m in range(1,min(27,(end-start)//k+1)):\n",
    "                d = k * m \n",
    "                q = deque()\n",
    "                c = 0  # 窗内有几种数字\n",
    "                cnt = [0]*26\n",
    "                for i in range(start,end):\n",
    "                    v = a[i]\n",
    "                    q.append(v)\n",
    "                    cnt[v] += 1\n",
    "                    if cnt[v] == 1:\n",
    "                        c += 1\n",
    "                    while cnt[v] > k or c > m or len(q) > d:\n",
    "                        p = q.popleft()\n",
    "                        cnt[p] -= 1 \n",
    "                        if not cnt[p]:\n",
    "                            c -= 1\n",
    "                    if len(q) == d :\n",
    "                        ans += 1\n",
    "            return ans \n",
    "\n",
    "\n",
    "        for i, v in enumerate(a):\n",
    "            if i and abs(v-a[i-1]) > 2:  # 重开一段\n",
    "                ans += f(start,i)\n",
    "                start = i \n",
    "           \n",
    "        \n",
    "        return ans "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
